package com.yiwenup.leetcode.offer;

import com.yiwenup.leetcode.RandomNode;

import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/
 **/
public class No035 {
    /**
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：37.8 MB, 在所有 Java 提交中击败了83.52%的用户
     */
    public RandomNode copyRandomList(RandomNode head) {
        if (head == null) return null;

        RandomNode cur = head;
        Map<RandomNode, RandomNode> map = new HashMap<>();
        while (cur != null) {
            map.put(cur, new RandomNode(cur.val));
            cur = cur.next;
        }

        cur = head;
        while (cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }

        return map.get(head);
    }
}
